import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-09
 * Time: 22:11
 */
class Solution {
//     dfs
//     注意剪枝
//     因为每个元素可以使用无数次
//     考虑当前元素 时 , index 不变
//     不考虑当前元素时 再 +1
    public int[] arr;
    public int length;
    public List<List<Integer>> lists=new ArrayList<>();
    public List<Integer> list=new ArrayList<>();
    public void dfs(int index, int sum, int target){
        // 剪枝
        if(index==length||sum>target){
            return ;
        }
        if(sum==target){
            lists.add(new ArrayList<>(list));
            return ;
        }
        // 考虑当前元素
        // 注意由于每个元素使用的次数不限制
        // 所以考虑过该元素之后, 可能还会使用, 所以 index 不变
        // 但一旦不考虑当前元素, 那么 index 就要 +1
        list.add(this.arr[index]);
        dfs(index, sum + this.arr[index], target);
        list.remove(list.size()-1);
        // 不考虑当前元素
        dfs(index+1, sum, target);
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.arr=candidates;
        this.length=candidates.length;
        dfs(0, 0, target);
        return lists;
    }
}
